NC40 两个链表生成相加链表

https://www.nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b6b

这题和 NC1 大数加法 的做法基本一致，只不过需要反转链表

func addInList(head1 *ListNode, head2 *ListNode) *ListNode {
    head1 = reversal(head1)
    head2 = reversal(head2)

    result := new(ListNode)
    tmp := result

    // 这题和 string 加法一样的操作
    add := 0 // 进位
    cur := 0 // 当前位的值
    for head1 != nil || head2 != nil || add != 0 {
        if head1 == nil && head2 != nil {
            cur = head2.Val + add
        } else if head1 != nil && head2 == nil {
            cur = head1.Val + add
        } else if head1 == nil && head2 == nil {
            cur = add
        } else {
            cur = head2.Val + head1.Val + add
        }

        if cur > 9 {
            add = cur / 10
            cur -= 10
        } else {
            add = 0
        }

        tmp.Next = &ListNode{Val: cur, Next: nil}
        tmp = tmp.Next

        if head1 != nil {
            head1 = head1.Next
        }

        if head2 != nil {
            head2 = head2.Next
        }
    }

  // 最后别忘了反转回来
    return reversal(result.Next)
}

// 反转链表
func reversal(head *ListNode) *ListNode {
    pre := head
    var cur *ListNode = nil

    for pre != nil {
        tmp := pre.Next
        pre.Next = cur
        cur = pre
        pre = tmp
    }

    return cur
}

时间复杂度 O(n) 空间复杂度 O(1)